#pragma once

#include <cstdint>
#include <type_traits>
#include <memory>
#include <cassert>
#include <initializer_list>

#include "Hash.h"
#include "ForwardLinkedList.h"
#include "Pair.h"


#include "Containers/Vector.h"
#include "Containers/ReflectableVector.h"


template <class T>
concept EqualCompare = requires(const T & Lhs, const T & Rhs)
{
	{ Lhs== Rhs } ->std::same_as<bool>;
};



template<typename KeyType, typename ValueType>
requires EqualCompare<KeyType> && WH::Hashable<KeyType>
class TMap;

template<typename KeyType,typename ValueType>
class TMapIterator
{
	using DataType= TPair<KeyType,ValueType>;
public:
	//end
	TMapIterator(){};

	TMapIterator(TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>* InMapData,uint64_t InIndex,typename TForwardForwardLinkedList< TPair<KeyType, ValueType>>::TNode * InNode)
	:Index(InIndex)
	,MapData(InMapData)
	,CurrentNode(InNode)
	{

	}

	DataType& operator*()
    {
        return **CurrentNode;
    }

    bool operator !=(const TMapIterator& Other)
    {
        return CurrentNode != Other.CurrentNode;
    }

    TMapIterator& operator ++()
    {
		CurrentNode=CurrentNode->Next;
		if(CurrentNode)
		{
			return *this;
		}

		do
		{
        	Index++;
		}
		while(Index<  MapData->Num() &&  (*MapData)[Index].Empty());

		if(Index<  MapData->Num())
		{
			CurrentNode=(*MapData)[Index].GetHead();
		}else
		{
			Index=0;
		}

        return *this;
    }

private:
	uint64_t Index;
	typename TForwardForwardLinkedList< TPair<KeyType, ValueType>>::TNode * CurrentNode=nullptr;

	TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>*  MapData;
};


//hash map
//to make a valid KeyType, you need implement :
//   (1) bool operator ==  
//   (2) uint64_t GetHashCode(const T&) or std::hash<KeyType> .
//   GetHashCode() can be or not be a member function   

//Custmize key example 1:
//struct CustmizeKey
//{
//    int a = 1;
//};
//
//bool operator ==(const CustmizeKey& L, constCustmizeKey& R)
//{
//    return L.a == R.a;
//}
//
//uint64_t  GetHashCode(const CustmizeKey& Value) { return std::hash<int>(Value.a); }

//Custmize key example 2:
//struct CustmizeKey
//{
//    float a = 1;
//    uint64_t GetHashCode()  const
//	  {
//		  return std::hash<float>(a);  
//	  }
//};
//
//bool operator ==(const CustmizeKey& L, constCustmizeKey& R)
//{
//    return L.a == R.a;
//}
//

//Custmize key example 3:
//struct A
//{
//    int a = 1;
//};
//
//bool operator ==(const A& L, const A& R)
//{
//    return L.a == R.a;
//}
//
//namespace std
//{
//    template<>
//    struct hash<A>
//    {
//        uint64_t operator ()(const A& Value)
//        {
//            return std::hash<int>()(Value.a);
//        }
//    };
//};
template<typename KeyType, typename ValueType>
requires EqualCompare<KeyType> && WH::Hashable<KeyType>
class TMap //:public CTMapBase
{
	
private:
	TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>> Data; 

	uint64_t Capacity = 1<<0;

	//how manay pair
	uint64_t Size = 0;
public:
	
	static TMap<KeyType, ValueType> Zip(const TVector<KeyType>& Keys, const TVector<ValueType>& Values)
	{	
		assert(Keys.Num() == Values.Num() && "Keys and Values must have same size");

		TMap<KeyType, ValueType> Ret(Keys.Num());
		for (uint64_t Index = 0; Index < Keys.Num(); ++Index)
		{
			Ret.Add(Keys[Index], Values[Index]);
		}

		return Ret;
	}

	TMap()	
	{	
		Capacity=16;
		Data = TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>::CreateFilledVector(Capacity);
	}

	TMap(uint64_t InitialCapacity)	
	{	
		while(Capacity<InitialCapacity)
		{
			Capacity=Capacity<<1;
		}
		Data = TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>::CreateFilledVector(Capacity);
	}

	TMap(std::initializer_list< TPair<KeyType, ValueType>> InValues)
	{
		while(Capacity<InValues.size())
		{
			Capacity=Capacity<<1;
		}
		
		Data = TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>::CreateFilledVector(Capacity);

		for(auto& Value:InValues)
		{
			Add(Value.Key,Value.Value);
		}

	}	

	int64_t Num() const
	{
		return Size;
	}

	bool Empty() const
	{
		return Size == 0;
	}

	template<typename ArgumentKeyType,typename ArgumentValueType >
	void Add(ArgumentKeyType&& InKey, ArgumentValueType&& InValue)
	{
		AddImpl(std::forward<ArgumentKeyType>(InKey),std::forward<ArgumentValueType>(InValue));
	}

	void AddImpl( KeyType&& InKey, ValueType&& InValue)
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				Node.Value = std::move(InValue);
				MakeSureCapacityLargeEnough();

				return;
			}
		}

		TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>* NewListNode = 
			new TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>(
				new TPair<KeyType, ValueType>{
					std::forward<KeyType>(InKey)
					, std::forward<ValueType>(InValue)
				}
			);
		Data[ArrayIndex].InsertAtHead(NewListNode);
		Size++;
		MakeSureCapacityLargeEnough();
	}

	void AddImpl(
		const KeyType & InKey
		, const ValueType & InValue)
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				Node.Value = InValue;
				MakeSureCapacityLargeEnough();

				return;
			}
		}

		TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>* NewListNode 
			= new TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>(
				new TPair<KeyType, ValueType>{InKey, InValue}
			);
		Data[ArrayIndex].InsertAtHead(NewListNode);
		Size++;
		MakeSureCapacityLargeEnough();
	}

	void AddImpl(const KeyType & InKey, ValueType&& InValue)
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				Node.Value = std::move(InValue);
				MakeSureCapacityLargeEnough();

				return;
			}
		}

		TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>* NewListNode 
			= new TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>(
				new TPair<KeyType, ValueType>{
					InKey
					, std::forward<ValueType>(InValue)
				}
			);
		Data[ArrayIndex].InsertAtHead(NewListNode);
		Size++;
		MakeSureCapacityLargeEnough();
	}

	void AddImpl(KeyType&& InKey, const ValueType & InValue)
	{
		uint64_t Hash = WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				Node.Value = InValue;
				MakeSureCapacityLargeEnough();

				return;
			}
		}

		TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>* NewListNode 
			= new TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>(
				new TPair<KeyType, ValueType>{
					std::forward<KeyType>(InKey)
					, InValue
				}
			);
		Data[ArrayIndex].InsertAtHead(NewListNode);
		Size++;
		MakeSureCapacityLargeEnough();
	}

	//find or add
	ValueType& FindOrAdd(const KeyType& InKey)
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				return Node.Value;
			}
		}

		TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>* NewListNode 
			= new TForwardForwardLinkedListNode< TPair<KeyType, ValueType>>(
				new TPair<KeyType, ValueType>(InKey, ValueType())
			);
		Data[ArrayIndex].InsertAtHead(NewListNode);
		Size++;
		MakeSureCapacityLargeEnough();

		return (*NewListNode)->Value;
	}


	bool Contains(const KeyType& InKey) const
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				return true;
			}
		}
		return false;
	}


	ValueType& operator [] (const KeyType& InKey)
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				return Node.Value;
			}
		}

		assert(false && "No such key");
		return (*Data[ArrayIndex].GetHead())->Value;
	}

	const ValueType& operator [] (const KeyType& InKey) const
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				return Node.Value;
			}
		}

		assert(false && "No such key");
		return (*Data[ArrayIndex].GetHead())->Value;
	}

	
	ValueType* Find(const KeyType& InKey) const
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		for (auto& Node : Data[ArrayIndex])
		{
			if (Node.Key == InKey)
			{
				return &Node.Value;
			}
		}

		return nullptr;
	}


	void Remove(const KeyType& InKey)
	{
		uint64_t Hash =  WH::GetHashCode(InKey);
		uint64_t ArrayIndex = Hash & (Capacity - 1);

		if (Data[ArrayIndex].Empty())
		{
			return;
		}

		TForwardForwardLinkedListIterator< TPair<KeyType, ValueType>> FormerNode = Data[ArrayIndex].end();
		for (TForwardForwardLinkedListIterator< TPair<KeyType, ValueType>> It = Data[ArrayIndex].begin();
			 It != Data[ArrayIndex].end();
			 FormerNode=It, ++It)
		{
			if (It->Key == InKey)
			{
				if (FormerNode!= Data[ArrayIndex].end())
				{
					Data[ArrayIndex].RemoveOneAfter(FormerNode);
				}
				else
				{
					Data[ArrayIndex].RemoveFirst();
				}
				Size--;
				return;
			}
		}
	}

	//remove by iterator
	void Remove(TMapIterator<KeyType,ValueType> It)
	{
		if(It==end())
		{
			return;
		}

		uint64_t ArrayIndex=It.ArrayIndex;
		TForwardForwardLinkedListIterator< TPair<KeyType, ValueType>> FormerNode = Data[ArrayIndex].end();
		for (TForwardForwardLinkedListIterator< TPair<KeyType, ValueType>> It2 = Data[ArrayIndex].begin();
			 It2 != Data[ArrayIndex].end();
			 FormerNode=It2, ++It2)
		{
			if (It2==It.Node)
			{
				if (FormerNode!= Data[ArrayIndex].end())
				{
					Data[ArrayIndex].RemoveOneAfter(FormerNode);
				}
				else
				{
					Data[ArrayIndex].RemoveFirst();
				}
				Size--;
				return;
			}
		}
	}

	void Clear()
	{
		Data = TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>::CreateFilledVector(Capacity);

		Size=0;
	}


	TMapIterator<KeyType,ValueType> begin() const
	{
		for(uint64_t Index=0;Index<Data.Num() ;++Index)
		{
			if(!Data[Index].Empty())
			{
				TMapIterator<KeyType,ValueType> It((TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>*)(&Data),Index,Data[Index].GetHead());

				return It;
			}
		}
		return end();
	}

	TMapIterator<KeyType,ValueType> end() const
	{
		return TMapIterator<KeyType,ValueType>();
	}

	TVector<KeyType> Keys() const
	{
		TVector<KeyType> Ret;
		Ret.Reserve(Size);

		for(auto& List: Data)
		{
			for(auto & Pair: List)
			{
				Ret.Add(Pair.Key);
			}
		}
		return Ret;
	}

	TVector<TVector<KeyType>> DebugKeys() const
	{
		TVector<TVector<KeyType>> Ret;

		for(auto& List: Data)
		{
			TVector<KeyType> Keys;
			for(auto & Pair: List)
			{
				Keys.Add(Pair.Key);
			}

			Ret.Add(Keys);
		}
		return Ret;

	}

	TVector<ValueType> Values() const
	{
		TVector<ValueType> Ret;
		Ret.Reserve(Size);
		
		for(auto& List: Data)
		{
			for(auto & Pair: List)
			{
				Ret.Add(Pair.Value);
			}
		}
		return Ret;
	}

	void ForEach(std::function<void(const KeyType&, ValueType&)> Func)
	{
		for (auto& List : Data)
		{
			for (auto& Pair : List)
			{
				Func(Pair->Key, Pair->Value);
			}
		}
	}

	void ForEach(std::function<void(const KeyType&, const ValueType&)> Func)const
	{
		for (auto& List : Data)
		{
			for (auto& Pair : List)
			{
				Func(Pair->Key, Pair->Value);
			}
		}
	}

	void RemoveAll(std::function<bool(const KeyType&, const ValueType&)> Func)
	{
		for (auto& List : Data)
		{
			TForwardForwardLinkedListIterator< TPair<KeyType, ValueType>> FormerNode = List.end();
			for (TForwardForwardLinkedListIterator< TPair<KeyType, ValueType>> It = List.begin();
				It != List.end();
				)
			{
				if (Func((*It)->Key, (*It)->Value))
				{	
					++It;

					if (FormerNode != List.end())
					{
						List.RemoveOneAfter(FormerNode);
					}
					else
					{
						List.RemoveFirst();
					}
					Size--;
				}
				else
				{
					FormerNode = It;
					++It;
				}
			}
		}
	}	

private:

	void MakeSureCapacityLargeEnough()
	{
		if (Size > Capacity)
		{
			Capacity=Capacity << 1;

			TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>> NewData= TVector<TForwardForwardLinkedList< TPair<KeyType, ValueType>>>::CreateFilledVector(Capacity);

			for (uint64_t ArrayIndex=0; ArrayIndex<Data.Num(); ArrayIndex++)
			{
				if (Data[ArrayIndex].Empty())
				{
					continue;
				}

				uint64_t NewArrayIndex0 = ArrayIndex ;
				uint64_t NewArrayIndex1 = NewArrayIndex0 + (Capacity>>1);
				
				while (!Data[ArrayIndex].Empty())
				{
					TForwardForwardLinkedListNode< TPair<KeyType, ValueType>> * Node = Data[ArrayIndex].PopNode();
					
					uint64_t Hash =  WH::GetHashCode((*Node)->Key);
					if ((Hash & (Capacity - 1)) == NewArrayIndex0)
					{
						NewData[NewArrayIndex0].InsertAtHead(Node);
					}
					else
					{
						NewData[NewArrayIndex1].InsertAtHead(Node);
					}
				}
			}

			Data =std::move(NewData);
		}
	}
};
